package Other;

public class leet_33 {
}

class Solution_33 {
    public int search(int[] nums, int target) {
        return 0;
    }



    public int doubleLinkSearch(int[] nums, int target){
        boolean direction = true;
        if(target < nums[0]){
            // 当 target 小于旋转后的第一个值
            // 从后往前找更加快
            direction = false;
        }

        if(direction){
            if(target==nums[0]){
                return 0;
            }

            // 正序 target > nums[0]
            for(int i=1; i<nums.length; i++){
                int lastNum = nums[i-1];
                int nowNum = nums[i];
                if(lastNum > nowNum || nowNum>target){
                    // 当前一个比后一个大时
                    // 该点旋转点，此时都没有找到匹配的那后面肯定没有了
                    // 或者 target < 当前值 代表后面肯定没有了
                    return -1;
                }
                if(nowNum==target){
                    return i;
                }
            }
        }else{
            if(target==nums[nums.length-1]){
                return nums.length-1;
            }

            // 反序匹配
            int maxIndex = nums.length-2;
            for(int i=maxIndex; i>-1; i--){
                int lastNum = nums[i+1];
                int nowNum = nums[i];
                if(nowNum>lastNum || nowNum<target){
                    // 前一个值小于本身时
                    // 该点是旋转点 此时都没有找到匹配的那后面肯定没有了
                    // 或者此时我小于目标值  代表倒序 也不存在有目标值了
                    return -1;
                }
                if(nowNum==target){
                    return i;
                }

            }

        }
        return -1;
    }

}
